package com.sheng.leetcode.year2023.month08.day17;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/8/17
 * <p>
 * 1444. 切披萨的方案数<p>
 * <p>
 * 给你一个 rows x cols 大小的矩形披萨和一个整数 k ，<p>
 * 矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。<p>
 * 切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，<p>
 * 将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，<p>
 * 那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。<p>
 * 请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。<p>
 * <p>
 * 示例 1：<p>
 * 输入：pizza = ["A..","AAA","..."], k = 3<p>
 * 输出：3<p>
 * 解释：上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。<p>
 * <p>
 * 示例 2：<p>
 * 输入：pizza = ["A..","AA.","..."], k = 3<p>
 * 输出：1<p>
 * <p>
 * 示例 3：<p>
 * 输入：pizza = ["A..","A..","..."], k = 1<p>
 * 输出：1<p>
 * <p>
 * 提示：<p>
 * 1 <= rows, cols <= 50<p>
 * rows == pizza.length<p>
 * cols == pizza[i].length<p>
 * 1 <= k <= 10<p>
 * pizza 只包含字符 'A' 和 '.' 。<p>
 */
public class LeetCode1444 {

    @Test
    public void test01() {
//        String[] pizza = {"A..", "AAA", "..."};
//        int k = 3;
//        String[] pizza = {"A..", "AA.", "..."};
//        int k = 3;
        String[] pizza = {"A..", "A..", "..."};
        int k = 1;
        System.out.println(new Solution().ways(pizza, k));
    }
}

class Solution {

    final int M = (int) 1e9 + 7;

    int m, n;

    int[][][] cache;

    public int ways(String[] pizza, int k) {
        // 假设：一个 m * n 的矩阵，有几种切法？m + n - 2 种切法
        m = pizza.length;
        n = pizza[0].length();
        // 二维前缀和，preSum[i][j] 表示 (0 ,0) 左上角，(i - 1 ,j - 1) 右下角的子矩阵苹果总数
        int[][] preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                // 计算矩阵内包含的苹果数
                preSum[i][j] = (pizza[i - 1].charAt(j - 1) == 'A' ? 1 : 0) + preSum[i][j - 1] + preSum[i - 1][j] - preSum[i - 1][j - 1];
            }
        }
        cache = new int[m][n][k];
        for (int x = 0; x < m; ++x) for (int y = 0; y < n; ++y) for (int z = 0; z < k; ++z) cache[x][y][z] = -1;
        return ways(preSum, 0, 0, k - 1);
    }

    /**
     * (x, y)：这块披萨的左上角坐标  remain：还要切几刀  返回值：这块披萨切分remain刀的方案数
     *
     * @param preSum preSum
     * @param x      左上角坐标的 x 轴
     * @param y      左上角坐标的 y 轴
     * @param remain 还要切几刀
     * @return 这块披萨切分remain刀的方案数
     */
    public int ways(int[][] preSum, int x, int y, int remain) {
        // 这块披萨最多只能切这么多刀，不够切了
        if (m - 1 - x + n - 1 - y < remain) {
            return 0;
        }
        // 苹果数量少于目标块数
        if (calc(preSum, x, y, m - 1, n - 1) < remain + 1) {
            return 0;
        }
        if (remain == 0) {
            return 1;
        }
        if (cache[x][y][remain] != -1) {
            return cache[x][y][remain];
        }

        int ret = 0;
        // 尝试横着切一刀，分为 [x : i] 行和 [i + 1 : m - 1] 行
        for (int i = x; i < m - 1; ++i) {
            int pizzaNum = calc(preSum, x, y, i, n - 1);
            // 确保切下来的这块有苹果
            if (pizzaNum > 0) {
                ret += ways(preSum, i + 1, y, remain - 1);
                ret %= M;
            }
        }
        // 尝试竖着切一刀，分为 [y : i] 列和 [i + 1 : n - 1] 列
        for (int i = y; i < n - 1; ++i) {
            int pizzaNum = calc(preSum, x, y, m - 1, i);
            if (pizzaNum > 0) {
                ret += ways(preSum, x, i + 1, remain - 1);
                ret %= M;
            }
        }
        cache[x][y][remain] = ret;
        return ret;
    }

    // 计算左上角 (x1, y1)，右下角 (x2, y2) 的子矩阵元素和
    public int calc(int[][] preSum, int x1, int y1, int x2, int y2) {
        return preSum[x2 + 1][y2 + 1] - preSum[x2 + 1][y1] - preSum[x1][y2 + 1] + preSum[x1][y1];
    }
}

